package com.zhanghp.class03;

import com.zhanghp.utils.CommonUtils;

/**
 * <h1>单链表 实现 队列 & 栈</h1>
 *
 * @author zhanghp
 * @date 2023-10-10 08:03
 */
public class Code02_LinkedListToQueueAndStatck {

    public static class Node<V>{
        public V value;
        public Node<V> next;

        public Node(V v){
            value = v;
            next = null;
        }
    }

    public static void main(String[] args) {
        // 队列
        MyQueue<Integer> queue = new MyQueue<>();
        // 添加元素
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        queue.print();
        // 查看头元素
        queue.peek();
        queue.print();
        // 弹出头元素
        queue.poll();
        queue.print();
        // 弹出头元素
        queue.poll();
        queue.print();

        CommonUtils.printDivingLine();

        // 栈
        MyStack<Integer> stack = new MyStack<>();
        stack.push(4);
        stack.push(3);
        stack.push(2);
        stack.push(1);
        stack.push(0);
        stack.printStack();

        stack.peek();
        stack.printStack();
        stack.poll();
        stack.poll();
        stack.printStack();

    }

    /**
     * <p>队列：先进先出，支持出，支持进</p>
     * <p>通过单链表实现</p>
     *
     * @param <V> 值类型
     */
    public static class MyQueue<V>{
        public Node<V> head;
        public Node<V> tail;
        public int size;

        public MyQueue(){
            head = null;
            tail = null;
            size = 0;
        }

        public boolean isEmpty(){
            return size == 0;
        }

        public int size(){
            return size;
        }

        /**
         * <p>添加一个元素</p>
         *
         * @param v 元素值
         */
        public void offer(V v){
            Node<V> cur = new Node<>(v);
            if (tail == null) {
                head = cur;
                tail = cur;
            }else {
                // 把上一个cur的next指向当前的值
                tail.next = cur;
                // 再把尾部重新指向当前值
                tail = cur;
            }
            size ++;
        }

        /**
         * <p>将队列中首个元素弹出，队列为空则为null</p>
         *
         * @return 首个元素
         */
        public V poll(){
            if (head == null) {
                return null;
            }else {
                head = head.next;
                size --;
                return head.value;
            }
        }

        /**
         * <p>查看队列中首个元素，不会移除</p>
         *
         * @return 首个元素
         */
        public V peek(){
            if (head==null) {
                return null;
            }else {
                return head.value;
            }
        }

        /**
         * <p>打印队列中的所有元素</p>
         */
        public void print(){
            if (head == null) {
                System.out.printf("%s%n", "队列为空");
            }else {
                Node<V> cur = head;
                while (cur != null) {
                    System.out.printf("%s ", cur.value);
                    cur = cur.next;
                }
                System.out.println();
            }
        }
    }

    public static class MyStack<V>{
        public Node<V> head;
        public int size;

        public void push(V v){
            Node<V> cur = new Node<>(v);
            if (head == null) {
                head = cur;
            }else {
                // 最后进的先出去，所以为头
                cur.next = head;
                head = cur;
            }
            size ++;
        }

        public V poll(){
            V ans = null;
            if (head == null) {
                return ans;
            }
            ans = head.value;
            head =head.next;
            return ans;
        }

        public V peek(){
            return head == null ? null : head.value;
        }

        public boolean isEmpty(){
            return size == 0;
        }

        public int size(){
            return size;
        }

        public void printStack(){
            if (head == null) {
                System.out.printf("%s%n", "栈为空");
                return;
            }
            Node<V> cur = head;
            do{
                System.out.printf("%s ", cur.value);
                cur = cur.next;
            }while (cur != null);
            System.out.println();
        }



    }

}
